package com.gitee.ywj1352.算法.期中考试;


import java.util.*;

public class 第一题目 {
    static HashSet<String> set = new HashSet<>();

    /**
     * 输入: [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。
     * 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     *
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int min = Integer.MAX_VALUE;
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        int[] a = new int[3];
        a[0] = 0; //当前index
        a[1] = nums[0];//当前值
        a[2] = 0; // 步数
        queue.addLast(a);
        while (!queue.isEmpty()) {
            int[] ints = queue.removeFirst();
            int curIdx = ints[0];
            int curVal = ints[1];
            int curCount = ints[2];
            for (int i = 1; i <= curVal; i++) {
                int nextIdx = curIdx + i;
                if (nextIdx == nums.length - 1) {
                    min = Math.min(min, curCount + 1);
                }
                if (nextIdx < nums.length) {
                    int[] cel = new int[3];
                    cel[0] = nextIdx;
                    cel[1] = nums[nextIdx];
                    cel[2] = curCount + 1;
                    queue.addFirst(cel);
                }
            }
        }
        return min;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(8));

    }


    public static int mySqrt(int x) {
        if(x ==1) return 1;
        long l = 0 , r = x,mid = x/2;
        while(l <= r){
            mid = l + (r -l ) /2;
            if(x  > (mid * mid) ){
                l = mid + 1;
            }
            if(x  < (mid * mid)){
                r = mid - 1;
            }
            if(x == mid * mid) return (int)mid;
        }
        return (int)mid;
    }
}
